package datastructure;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 *
 * @author liuziyang
 * @create 2019-11-05 21:56
 */
public class MyPriorityQueue {
    private int[] array;
    private int size;

    public MyPriorityQueue() {
        // 队列的初始长度是32
        array = new int[32];
    }

    public static void main(String[] args) throws Exception {
        MyPriorityQueue queue = new MyPriorityQueue();
        queue.enQueue(3);
        queue.enQueue(5);
        queue.enQueue(10);
        queue.enQueue(2);
        queue.enQueue(7);
        System.out.println(queue.deQueue());
        System.out.println(queue.deQueue());
    }

    /**
     * 入队
     *
     * @param key
     */
    public void enQueue(int key) {
        //队列长度超出范围，扩容
        if (size >= array.length) {
            resize();
        }

        array[size++] = key;
        upAdjust();
    }

    /**
     * 出队
     *
     * @return
     */
    public int deQueue() throws Exception {
        if (size <= 0) {
            throw new Exception("the queue is empty!");
        }

        //获取堆顶元素
        int head = array[0];
        // 让最后一个元素移动到堆顶
        array[0] = array[--size];
        downAdjust();
        return head;
    }

    /**
     * 上浮调整
     */
    private void upAdjust() {
        int childIndex = size - 1;
        int parentIndex = (childIndex - 1) / 2;
        // temp保存的是插入的叶子节点值，用于最后的赋值
        int temp = array[childIndex];
        while (childIndex > 0 && temp > array[parentIndex]) {
            //无需真正交换，单向赋值即可
            array[childIndex] = array[parentIndex];
            childIndex = parentIndex;
            parentIndex = childIndex / 2;
        }

        array[childIndex] = temp;
    }

    /**
     * 下沉调整
     */
    private void downAdjust() {
        // temp保存父节点的值，用于最终的赋值
        int parentIndex = 0;
        int temp = array[parentIndex];
        int childIndex = 1;
        while (childIndex < size) {
            // 如果有右孩子节点，且有孩子节点大于左孩子节点，定位到右孩子节点
            if (childIndex + 1 < size && array[childIndex] < array[childIndex + 1]) {
                childIndex++;
            }

            //如果父节点大于任何一个孩子节点，则直接跳出循环
            if (temp > array[childIndex]) {
                break;
            }

            //无需真正交换，单向赋值即可
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = parentIndex * 2 + 1;
        }

        array[parentIndex] = temp;
    }

    private void resize() {
        //队列容量翻倍
        int newSize = size * 2;
        this.array = Arrays.copyOf(this.array, newSize);
    }
}
